#include "doubleLinkList.h"
#include <iostream>
doubleLinkList::doubleLinkList():size(0)
{
    head=tail=new Node(0);
    Free = nullptr;
}

doubleLinkList::doubleLinkList(const doubleLinkList &d)
{
    size=d.size;
    head=tail=new Node(0);
    Node *tp=head;
    Node *travelPoint = d.head->next;
    while(travelPoint!=nullptr){
        Node *newNode=new Node(travelPoint->value);
        tail=newNode;
        tp->next=newNode;//入链
        newNode->prev=tp;
        tp=tp->next;//遍历
        travelPoint=travelPoint->next;
    }
}

doubleLinkList &doubleLinkList::operator=(const doubleLinkList &d)
{
    while(head!=nullptr){
        Node *nextNode=head->next;//下一个节点存下来
        delete head;
        head=nextNode;
    }
    tail=nullptr;
    size=d.size;
    head=tail=new Node(0);
    Node *tp=head;
    Node *travelPoint = d.head->next;
    while(travelPoint!=nullptr){
        Node *newNode=new Node(travelPoint->value);
        tail=newNode;
        tp->next=newNode;//入链
        newNode->prev=tp;
        tp=tp->next;//遍历
        travelPoint=travelPoint->next;
    }
    return *this;
}

doubleLinkList::~doubleLinkList()
{
    while(head!=nullptr){
        Node *nextNode=head->next;//下一个节点存下来
        if(Free)
            free(head->value);
        delete head;
        head=nextNode;
    }
    tail=nullptr;
}

void doubleLinkList::insertTail(const elementType &element) //O(1)
{
    Node *newNode = new Node(element);
    tail->next=newNode;
    newNode->prev=tail;
    tail=newNode;
    size++;
}

void doubleLinkList::insertByIndex(size_t index, const elementType &element)
{
    if(index>size){
        std::cout<<"位置非法\n";
        return;
    }
    Node *travelPoint =head;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    Node *newNode=new Node(element);
    newNode->next=travelPoint->next;
    newNode->prev=travelPoint;
    if(size!=0)
        travelPoint->next->prev=newNode;//防止当有且仅有head结点时，对head->next->prev操作会发生段错误
    travelPoint->next=newNode;
    size++;
}

void doubleLinkList::removeByIndex(size_t index)
{
    if(index>=size){
        std::cout<<"删除位置非法\n";
        return;
    }
    Node *travelPoint=head;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    Node *freeNode =travelPoint->next;
    travelPoint->next=freeNode->next;
    if(freeNode->next!=nullptr)
        freeNode->next->prev=travelPoint;
    else{
        tail=travelPoint;
    }
    if(Free)
        Free(freeNode->value);
    delete freeNode;
    size--;
}

void doubleLinkList::removeByElement(const elementType &element)
{
    Node *travelPoint=head;
    while(travelPoint->next!=nullptr){ //tp不到尾部
        if(compare(travelPoint->next->value,element)){
            Node *freeNode =travelPoint->next;
            travelPoint->next=freeNode->next;//转接
            if(freeNode->next!=nullptr)
                freeNode->next->prev=travelPoint;
            else{
                tail=travelPoint;
            }
            if(Free)
                Free(freeNode->value);
            delete freeNode;
            size--;
        }
        else
            travelPoint=travelPoint->next;
    }
}

doubleLinkList::elementType *doubleLinkList::findByIndex(size_t index)
{
    if(index>=size)
        return nullptr;
    Node *travelPoint=head->next;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    return &travelPoint->value;
}

// DARRAY::dynamicArray doubleLinkList::findByElement(const elementType &element)
// {
//     DARRAY::dynamicArray array;
//     Node *travelPoint=head->next;
//     while(travelPoint!=nullptr){
//         if(compare(travelPoint->value,element))
//             array.insertTail(&travelPoint->value);
//         travelPoint=travelPoint->next;
//     }
//     return array;
// }

void doubleLinkList::updateByIndex(size_t index, const elementType &element)
{
    if(index>=size){
        std::cout<<"位置非法\n";
        return;
    }
    Node *travelPoint=head->next;
    for(size_t i=0;i<index;i++){
        travelPoint=travelPoint->next;
    }
    travelPoint->value=element;
}

void doubleLinkList::updateByElement(const elementType &oldValue, const elementType &newValue)
{
    Node *travelPoint=head->next;
    while(travelPoint!=nullptr){
        if(compare(travelPoint->value,oldValue))
            travelPoint->value=newValue;
        travelPoint=travelPoint->next;
    }
}

void doubleLinkList::sort()
{
    fastSort(head->next,tail);
}

void doubleLinkList::show()
{
    std::cout<<"size:"<<size<<std::endl;
    Node *travelPoint=head->next;
    while(travelPoint!=nullptr){//链表还没结束
        print(travelPoint->value);
        travelPoint=travelPoint->next;//遍历指针往后走
    }
    std::cout<<"逆序显示:"<<std::endl;

    travelPoint=tail;
    while(travelPoint!=head){
        print(travelPoint->value);
        travelPoint=travelPoint->prev;
    }

}

void doubleLinkList::fastSort(Node *start, Node *end)
{
    if(start==end||start==end->next)//终止条件
        return;
    Node* left=start;
    Node* right=end;
    elementType temp =start->value;
    while(left!=right){
        while(cmpBig(right->value,temp)&&left!=right)
            right=right->prev;
        if(left!=right){
            left->value=right->value;
            left=left->next;
        }
        while(cmpBig(temp,left->value)&&left!=right)
            left=left->next;
        if(left!=right){
            right->value=left->value;
            right=right->prev;
        }
    }
    left->value=temp;
    fastSort(start,right->prev);
    fastSort(left->next,end);
}

size_t doubleLinkList::Size()
{
    return size;
}
